import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;

public class EfficientMedianFilter {

	// public static double[][] fastFilter(double[][] map) {
	//
	// int xDim = map.length;
	// int yDim = map[0].length;
	// int maskSize = 5;
	// int medianPos = ((maskSize * maskSize + 1) / 2) - 1;
	// double[][] newArray = new double[xDim][yDim];
	//
	// for (int x = 0; x < newArray.length; x++) {
	//
	// // the first y mask is computed manually;
	// int firstY = 0;
	// double[][] elements = getElements(map, xDim, yDim, maskSize, x, firstY);
	//
	// Arrays.sort(elements, new Comparator<double[]>() {
	// @Override
	// public int compare(double[] o1, double[] o2) {
	// if (o1[2] > o2[2])
	// return 0;
	// else
	// return 1;
	// }
	// });
	// newArray[x][firstY] = elements[medianPos][2]; // median
	//
	// // all further ys will be added/deleted
	// for (int y = 1; y < newArray[0].length; y++) {
	// elements = getNextElements(elements, map, xDim, yDim, maskSize, x, y);
	// newArray[x][y] = elements[medianPos][2];
	// }
	// }
	// return (newArray);
	// }
	//
	// private static double[][] getElements(double[][] map, int xDim, int yDim, int maskSize, int x, int y) {
	// int i = 0;
	// int maskRadius = (maskSize - 1) / 2;
	// // x/y/intensity
	// double[][] elements = new double[maskSize * maskSize][3];
	//
	// for (int mx = maskRadius * -1; mx <= maskRadius; mx++) {
	// for (int my = maskRadius * -1; my <= maskRadius; my++) {
	// elements[i][0] = mx;
	// elements[i][1] = my;
	// if ((x + mx >= 0) && (y + my >= 0) && (x + mx < xDim) && (y + my < yDim)) {
	// elements[i][2] = map[x + mx][y + my];
	// } else
	// elements[i][2] = 0;
	// i++;
	// }
	// }
	// return elements;
	// }
	//
	// private static double[][] getNextElements(double[][] elements, double[][] map, int xDim, int yDim, int maskSize, int x, int y) {
	//
	// int lastColumnIndex = elements.length;
	//
	// for (int i = 0; i < elements[0].length; i++) {
	// elements
	// }
	//
	// return null;
	// }

	public static double[][] slowFilter(double[][] map) {

		int xDim = map.length;
		int yDim = map[0].length;
		int maskSize = 5;
		int maskR = (maskSize - 1) / 2;
		int medianPos = ((maskSize * maskSize + 1) / 2) - 1;
		int eC;
		double[][] newArray = new double[xDim][yDim];
		double[] elements = new double[maskSize * maskSize];

		for (int x = 0; x < newArray.length; x++) {
			for (int y = 0; y < newArray[0].length; y++) {
				eC = 0;
				for (int mx = maskR * -1; mx <= maskR; mx++) {
					for (int my = maskR * -1; my <= maskR; my++) {
						if ((x + mx >= 0) && (y + my >= 0) && (x + mx < xDim) && (y + my < yDim)) {
							elements[eC] = map[x + mx][y + my];
						} else
							elements[eC] = 0;
						eC++;
					}
				}
				Arrays.sort(elements);
				newArray[x][y] = elements[medianPos]; // median
			}
		}
		return (newArray);
	}

	public static double[][] multithreadFilter(final double[][] map) {

		int xDim = map.length;
		int yDim = map[0].length;
		final int maskSize = 5;
		final int medianPos = ((maskSize * maskSize + 1) / 2) - 1;
		double[][] newArray = new double[xDim][yDim];
		

		for (int x = 0; x < newArray.length; x++) {
			MedianLineProcessor t = new MedianLineProcessor(map, maskSize, medianPos, newArray, x);
			t.start();
		}
		return (newArray);
	}

	static class MedianLineProcessor extends Thread{
		private double[][] map;
		private int maskSize;
		private int medianPos;
		private double[][] newArray;
		private int x;
		
		public MedianLineProcessor(double[][] map, int maskSize, int medianPos, double[][] newArray, int x) {
			super();
			this.map = map;
			this.maskSize = maskSize;
			this.medianPos = medianPos;
			this.newArray = newArray;
			this.x = x;
		}

		@Override
		public void run() {
			double[] elements = new double[maskSize * maskSize];
			for (int y = 0; y < newArray[0].length; y++) {
				newArray[x][y] = getMedianOfArea(map, maskSize, medianPos, elements, x, y);
			}
		}
	}
	
	private static void processLine(final double[][] map,final  int maskSize,final  int medianPos, double[][] newArray, int x) {
		double[] elements = new double[maskSize * maskSize];
		for (int y = 0; y < newArray[0].length; y++) {
			newArray[x][y] = getMedianOfArea(map, maskSize, medianPos, elements, x, y);
		}
	}

	private static double getMedianOfArea(final double[][] map, final int maskSize, final int medianPos, double[] elements, int x, int y) {
		final int xDim = map.length;
		final int yDim = map[0].length;
		final int maskR = (maskSize - 1) / 2;
		int eC = 0;
		for (int mx = maskR * -1; mx <= maskR; mx++) {
			for (int my = maskR * -1; my <= maskR; my++) {
				if ((x + mx >= 0) && (y + my >= 0) && (x + mx < xDim) && (y + my < yDim)) {
					elements[eC] = map[x + mx][y + my];
				} else
					elements[eC] = 0;
				eC++;
			}
		}
		Arrays.sort(elements);
		return elements[medianPos]; // median
	}
	
	public static double[][] fastFilter(double[][] map) {

		int xDim = map.length;
		int yDim = map[0].length;
		int maskSize = 5;
		int maskR = (maskSize - 1) / 2;
		int medianPos = ((maskSize * maskSize + 1) / 2) - 1;
		int eC;
		double[][] newArray = new double[xDim][yDim];

		TreeMap<Integer, Double> tm = new TreeMap<Integer, Double>();


		for (int x = 0; x < newArray.length; x++) {
			for (int y = 0; y < newArray[0].length; y++) {
				eC = 0;
				for (int mx = maskR * -1; mx <= maskR; mx++) {

					for (int my = maskR * -1; my <= maskR; my++) {
						if ((x + mx >= 0) && (y + my >= 0) && (x + mx < xDim) && (y + my < yDim)) {
							tm.put(eC, map[x + mx][y + my]);
						} else
							tm.put(eC, (double) 0);
						eC++;
					}
				}

				
				Collection<Double> values = tm.values();
				Iterator<Double> iterator = values.iterator();
				int i = 0;
				while (((Iterator<?>) iterator).hasNext()) {
					Double next = iterator.next();
					if (i == medianPos) {
						newArray[x][y] = next;
						break;
					}
					i++;
				}

			}
		}
		return (newArray);
	}

}
